#include<bits/stdc++.h>

#define lowbit(x) x&(-x)
using namespace std;
using i64 = long long;
using pii = std::pair<int, int>;
constexpr i64 mod = 1000000000000037;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN_32 = 2e9;
constexpr i64 MAXN_64 = 1e18;

void solve() {
    int n;
    cin >> n;
    mt19937_64 rnd(random_device{}());
    vector<int> p(n + 1), P;
    for (int i = 2; i <= n; i++) {
        if (!p[i]) P.push_back(i);
        for (auto prime: P) {
            if (i * prime > n) break;
            p[i * prime] = 1;
            if (i % prime == 0) break;
        }
    }

    map<i64, int> mp;
    map<int, i64> dic;
    map<int, bool> isPrime;
    for (auto prime: P) {
        isPrime[prime] = 1;
        while (!dic[prime]) {
            dic[prime] = rnd() % mod;
        }
    }

    mp[0] = 1;
    auto gethash = [&](int x) {
        i64 cur = 0;
        for (auto prime: P) {
            if (prime > x) break;
            if (x % prime == 0) {
                cur = (cur + dic[prime]) % mod;
            }
            while (x % prime == 0) x /= prime;
        }
        return cur;
    };

    vector<i64> hash(n + 1);
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            if (i + i > n) {
                mp[0]++;
                continue;
            }
        }
        hash[i] = gethash(i);
        mp[hash[i]]++;
    }

    bool ok = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x) {
            if ((isPrime[x] || x == 1) && (isPrime[i] || i == 1) && (i + i > n || i == 1) && (x + x > n || x == 1)) {
                mp[0]--;
                continue;
            }
            i64 cur1 = hash[x], cur2 = hash[i];
            if (cur1 != cur2) ok = 0;
            mp[cur1]--;
        }
    }

    if (!ok) {
        cout << "0\n";
        return;
    }

    vector<i64> fac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = (fac[i - 1] * (i % MOD)) % MOD;
    }

    i64 ans = 1;
    for (auto &[key_, val_]: mp) {
        ans = (ans * fac[val_]) % MOD;
    }
    cout << ans << "\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    // int cc = clock();
    int t = 1;
    std::cin >> t;
    while (t--) solve();
    // cout << clock() - cc << "ms";
    // bf();
    return 0;
}